// 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

// 示例 1:

// 输入: s = "cbaebabacd", p = "abc"
// 输出: [0, 6]
// 解释:
// 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
// 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
//  示例 2:

// 输入: s = "abab", p = "ab"
// 输出: [0, 1, 2]
// 解释:
// 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
// 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
// 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams1 = function (s, p) {
    // 这种方法超时啦，不能暴力求解
    let temp = p;
    temp = temp.toLowerCase().split('').sort().join('');
    const len = temp.length;
    const res = [];
    for (let i = 0; i < s.length - len + 1; i++) {
        const str = s.substring(i, i + len).split('').sort().join('');
        if (str === temp)
            res.push(i);
    }
    return res;
};

var findAnagrams = function (s, p) {
    // 滑动窗口
    const sLen = s.length, pLen = p.length;
    if (sLen < pLen)
        return [];
    
    const res = [];
    const sCnt = new Array(26).fill(0);
    const pCnt = new Array(26).fill(0);

    for (let i = 0; i < pLen; i++) {
        sCnt[s[i].charCodeAt() - 'a'.charCodeAt()]++;
        pCnt[p[i].charCodeAt() - 'a'.charCodeAt()]++;
    }

    if (sCnt.join('') === pCnt.join(''))
        res.push(0);
    
    for (let i = 0; i < sLen - pLen; i++) {
        --sCnt[s[i].charCodeAt() - 'a'.charCodeAt()];
        ++sCnt[s[i + pLen].charCodeAt() - 'a'.charCodeAt()];
        if (sCnt.join('') === pCnt.join(''))
            res.push(i + 1);
    }
    return res;
};



const s = "cbaebabacd", p = "abc";
const ans = findAnagrams(s, p);
console.log(ans);